// https://www.lintcode.com/problem/lowest-common-ancestor-ii/

/**
 * Definition of ParentTreeNode:
 * 
 * class ParentTreeNode {
 *     public ParentTreeNode parent, left, right;
 * }
 */


public class Solution {
    /*
     * @param root: The root of the tree
     * @param A: node in the tree
     * @param B: node in the tree
     * @return: The lowest common ancestor of A and B
     */
    public ParentTreeNode lowestCommonAncestorII(ParentTreeNode root, ParentTreeNode A, ParentTreeNode B) {
        // write your code here
        HashSet<ParentTreeNode> set = new HashSet<>();
        while (A != null) {
            set.add(A);
            A = A.parent;
        }
        while (B != null) {
            if (set.contains(B)) {
                return B;
            }
            B = B.parent;
        }
        return null;
    }
}